package com.seu.data.structures.heapAndPriorityQueue.min;

/**
 * 自定义的整形最小堆
 * 实现基本的CRUD功能
 *
 * @author liangfeihu
 * @since 2020/6/13 00:20
 */
public class MyMinHeap implements MinHeapFace {
    /**
     * 最小堆的数据
     */
    private int[] data;
    /**
     * 最小堆的元素数
     */
    private int count;
    /**
     * 最小堆的容量
     */
    private int capacity;

    /**
     * 构造函数, 构造一个空堆, 可容纳capacity个元素
     */
    public MyMinHeap() {
        data = new int[20 + 1];
        count = 0;
        this.capacity = 20;
    }

    public MyMinHeap(int capacity) {
        data = new int[capacity + 1];
        count = 0;
        this.capacity = capacity;
    }

    /**
     * 构造函数, 通过一个给定数组创建一个最小堆
     * 该构造堆的过程, 时间复杂度为O(n)
     */
    public MyMinHeap(int[] arr) {
        int n = arr.length;

        data = new int[n + 1];
        capacity = n;

        for (int i = 0; i < n; i++) {
            data[i + 1] = arr[i];
        }
        count = n;

        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i);
        }
    }

    /**
     * 返回堆中的元素个数
     */
    @Override
    public int size() {
        return count;
    }

    /**
     * 返回一个布尔值, 表示堆中是否为空
     */
    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 向最小堆中插入一个新的元素
     * add int to MinHeap
     *
     * @param x
     */
    @Override
    public void add(int x) {
        // assert count + 1 <= capacity;
        /*if (count + 1 > capacity) {
            throw new IllegalArgumentException("Add failed.");
        }*/

        if (count >= capacity) {
            resize(2 * capacity);
        }

        data[count + 1] = x;
        count++;
        shiftUp(count);
    }

    /**
     * 获取最小堆中的堆顶元素
     * return but do not remove top of heap
     *
     * @return
     */
    @Override
    public int get() {
        // assert (count > 0);
        if (isEmpty()) {
            // throw new IllegalArgumentException("Get failed. Index is illegal.");
            System.err.println("empty min heap");
            return -1;
        }
        return data[1];
    }

    /**
     * 从最小堆中取出堆顶元素, 即堆中所存储的最小数据
     * remove top of heap
     */
    @Override
    public void remove() {
        // assert count > 0;
        if (isEmpty()) {
            return;
        }
        int ret = data[1];

        swap(1, count);
        count--;
        shiftDown(1);

        if (count == capacity / 4 && capacity / 2 != 0) {
            resize(capacity / 2);
        }
    }

    /**
     * replace top of heap with int
     *
     * @param x
     */
    @Override
    public void replace(int x) {
        data[1] = x;
        if (isEmpty()) {
            count++;
        } else {
            shiftDown(1);
        }
    }

    /**
     * remove everything from heap
     */
    @Override
    public void clear() {
        count = 0;
    }

    /**
     * 交换堆中索引为i和j的两个元素
     */
    private void swap(int i, int j) {
        if (i <= 0 || i > count || j <= 0 || j > count) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        int t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    /**
     * 将数组空间的容量变成newCapacity大小
     */
    private void resize(int newCapacity) {
        int[] newData = new int[newCapacity + 1];
        for (int i = 1; i <= count; i++) {
            newData[i] = data[i];
        }
        data = newData;
        capacity = newCapacity;
    }

    /**
     * 最小堆核心辅助函数: 上浮操作
     */
    private void shiftUp(int k) {
        while (k > 1 && data[k / 2] > data[k]) {
            swap(k, k / 2);
            k /= 2;
        }
    }

    /**
     * 最小堆核心辅助函数: 下沉操作
     */
    private void shiftDown(int k) {
        while (2 * k <= count) {
            int j = 2 * k;
            // 在此轮循环中,data[k]和data[j]交换位置
            if (j + 1 <= count && data[j + 1] < data[j]) {
                j++;
            }
            // data[j] 是 data[2*k]和data[2*k+1]中的最小值

            if (data[k] <= data[j]) {
                break;
            }
            swap(k, j);
            k = j;
        }
    }

    /**
     * 测试 MinHeap
     */
    public static void main(String[] args) {
        // 堆中元素个数
        int N = 10;
        MyMinHeap minHeap = new MyMinHeap(N);

        int[] arry = generateArry(N);
        System.out.println("原始数组元素：");
        printArry(arry);

        // 将数组元素加入最小堆
        for (int i = 0; i < N; i++) {
            minHeap.add(arry[i]);
        }

        int[] arr = new int[N];
        // 将minheap中的数据逐渐从堆顶取出来
        // 取出来的顺序应该是按照从小到大的顺序取出来的
        for (int i = 0; i < N; i++) {
            arr[i] = minHeap.get();
            minHeap.remove();
        }
        // 确保arr数组是从小到大排列的
        for (int i = 1; i < N; i++) {
            assert arr[i - 1] <= arr[i];
        }

        System.out.println("最小堆数据元素：");
        printArry(arr);

        // 将数组元素加入最小堆
        for (int i = 0; i < N; i++) {
            minHeap.add(arry[i]);
        }
        int newTop = (int) (Math.random() * 50);
        System.out.println("替换堆顶元素为:" + newTop);
        minHeap.replace(newTop);
        // 将minheap中的数据逐渐从堆顶取出来
        // 取出来的顺序应该是按照从小到大的顺序取出来的
        for (int i = 0; i < N; i++) {
            arr[i] = minHeap.get();
            minHeap.remove();
        }
        System.out.println("最小堆数据元素：");
        printArry(arr);

        // 将数组元素加入最小堆
        for (int i = 0; i < N; i++) {
            minHeap.add(arry[i]);
        }
        System.out.println("最小堆是否为空:" + minHeap.isEmpty() + " size=" + minHeap.size());
        minHeap.clear();
        System.out.println("清空最小堆后：");
        System.out.println("最小堆是否为空:" + minHeap.isEmpty() + " size=" + minHeap.size());
    }

    private static int[] generateArry(int num) {
        int[] arr = new int[num];
        // 堆中元素取值范围[0, M)
        int M = 100;
        for (int i = 0; i < num; i++) {
            arr[i] = ((int) (Math.random() * M));
        }
        return arr;
    }

    private static void printArry(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("----------------");
    }
}
